package cn.arnold.stack;

import java.util.ArrayList;
import java.util.List;

public class SuffixExpression {

    // 中缀表达式转为list
    public List<String> infixExptoList(String infix) {
        // 存放中缀表达式转化后的值
        List<String> list = new ArrayList<String>();
        int index = 0;    //遍历指针
        char c;         //每次遍历到的字符
        String str;     //用于拼接多位数
        do {
            // c是非数字则直接加入到list
            if ((c = infix.charAt(index)) < 48 || (c = infix.charAt(index)) > 57) {
                list.add("" + c);   // char转为String
                index++;
            } else { // c是数字则要考虑多位数
                str = "";
                while (index < infix.length() && (c = infix.charAt(index)) >= 48 && (c = infix.charAt(index)) <= 57) {
                    str += c; //拼接
                    index++;
                }
                list.add(str);
            }
        } while (index < infix.length());
        /*for (int i = 0; i < infix.length(); i++) {
            c = infix.charAt(i);
            // c是非数字则直接加入到list
            if (c < 48 || c > 57) {
                list.add("" + c);
            } else {
                // c是数字则要考虑多位数
                str = "";
                while (i < infix.length() && (c = infix.charAt(i)) >= 48 && (c = infix.charAt(i)) <= 57) {
                    str += c; //拼接
                    i++;
                }
                list.add(str);
            }
        }*/
        return list;
    }

    public List<String> phraseSuffixExpression(List<String> ls) {
        // 定义两个栈
        Stack s1 = new Stack(10);   // 运算符栈
        //因为s2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
        //因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> s2
        //Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2
        List<String> s2 = new ArrayList<String>();

        // 遍历ls
        for (String item : ls) {

            if (item.matches("\\d+")) {     // 遇到操作数时，将其压s2
                s2.add(item);
            } else if (item.equals("(")) {           //如果是左括号"("，则直接压入s1
                s1.push(item.charAt(0));
            } else if (item.equals(")")) {           //如果是右括号")"，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
                while (!s1.peek().equals("(")) {
                    s2.add("" + s1.pop());
                    //!!! 将 ( 弹出 s1栈， 消除小括号
                    s1.pop();
                }
            } else {                                 // 遇到运算符时，比较其与s1栈顶运算符的优先级
                //1.如果s1为空，或栈顶运算符为左括号"("，则直接将此运算符入栈；
                //2.否则，若优先级比栈顶运算符的高，也将运算符压入s1；
                //3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到（2.1）与s1中新的栈顶运算符相比较；
                //当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
                while (s1.isEmpty() == false && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                    s2.add("" + s1.pop());
                }
                //还需要将item压入栈
                s1.push(item.charAt(0));
            }
        }
        //将s1中剩余的运算符依次弹出并加入s2
        while (s1.isEmpty() == false) {
            s2.add("" + s1.pop());
        }
        return s2;
    }
}

//编写一个类 Operation 可以返回一个运算符 对应的优先级
class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    //写一个方法，返回对应的优先级数字
    public static int getValue(String operation) {
        int result = 0;
        if (operation == "+") {
            result = ADD;
        } else if (operation == "-") {
            result = SUB;
        } else if (operation == "*") {
            result = MUL;
        } else if (operation == "/") {
            result = DIV;
        } else {
            System.out.println("不存在该运算符" + operation);
        }
        return result;
    }
}